#include <iostream>
#include <vector>
using namespace std;

int search(vector<int>& nums, int target)
{
    if (nums.empty()) {
	return -1;
    }
    int left = 0, right = nums.size() - 1, mid = 0;
    while (left <= right) {
	mid = (left + right) / 2;
	if (nums[mid] == target) {
	    return mid;
	}
	if (nums[mid] >= nums[left]) //nums[mid]在前半段
	{
	    if (target < nums[mid] && target >= nums[left]) //满足此条件，说明targte可能在mid之前,即，target是处于排过序的那一段
	    {
		right = mid - 1;
	    } else {
		left = mid + 1;
	    }
	} else //nums[mid]在后半段
	{
	    if (target > nums[mid] && target <= nums[right]) {
		left = mid + 1;
	    } else {
		right = right - 1;
	    }
	}
    }
    return -1;
}

int main(int argc, char* argv[])
{

    return 0;
}
